package a1_p04_ak_fh;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.jgraph.graph.DefaultEdge;
import org.jgrapht.Graph;
import org.jgrapht.graph.SimpleGraph;

public class DepthFirstSearch {
	int access = 0;

	/**
	 * Factory method of the class
	 * @param graph
	 * @param startVertex
	 * @param endVertex
	 * @return Way of vertices from the startvertex to the endvertex
	 */
	public static List<String> DFS(Graph<String, DefaultEdge> graph,
			String startVertex, String endVertex) {
		DepthFirstSearch dfs = new DepthFirstSearch();
		
		return dfs.DepthFirstSearch(graph, startVertex, endVertex);
	}

	/**
	 * constructor of the class
	 * @param graph
	 * @param startVertex
	 * @param endVertex
	 * @return Way of vertices from the startvertex to the endvertex
	 */
	private List<String> DepthFirstSearch(Graph<String, DefaultEdge> graph,
			String startVertex, String endVertex) {

		Stack<String> path = new Stack<String>();
		Stack<String> shortestPath = new Stack<String>();

		path.push(startVertex);
		shortestPath = deepSearch(graph, endVertex, startVertex, path, shortestPath);

		System.out.println("Weglaenge: " + (shortestPath.size() - 1));
		System.out.println(access + " hits\n");

		return shortestPath;

	}

	/**
	 * recursive method to get the way to the endvertex
	 * @param graph
	 * @param endVertex
	 * @param vertex
	 * @param path
	 * @param foundPath
	 * @return the path to endvertex
	 */
	private Stack<String> deepSearch(Graph<String, DefaultEdge> graph, String endVertex,
			String vertex, Stack<String> path, Stack<String> shortestPath) {

		// System.out.println("Inspecting " + vertex);
		access++;

		// if the vertex is the endvertex -> found a way to the endvertex
		if (vertex.equals(endVertex)) {
			
			// empty OR shorter path
			if (shortestPath.isEmpty() || shortestPath.size() > path.size()) {
				shortestPath.clear();
				shortestPath.addAll(path);
			}
		} else {

			// All edges of the current vertex
			Set<DefaultEdge> edges = graph.edgesOf(vertex);

			// going through all edges of the current vertex
			for (DefaultEdge edge : edges) {

				String newVertex = graph.getEdgeTarget(edge);

				
				// simple grapth and the vertex has a loop
				if (graph instanceof SimpleGraph && vertex.equals(newVertex)) {
					newVertex = graph.getEdgeSource(edge);
				}

				// path has not the vertex in the list
				if (!path.contains(newVertex)) {

					path.push(newVertex);
					// System.out.println(path.toString());
					// search if there is a better way
					deepSearch(graph, endVertex, newVertex, path, shortestPath);
					path.pop();
				}

			}
		}
		return shortestPath;
	}
}
